<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
   "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<head>
    <title>colorizer Docs</title>
    <link rel="stylesheet" href="../ldoc.css" type="text/css" />
</head>
<body>

<div id="container">

<div id="product">
	<div id="product_logo"></div>
	<div id="product_name"><big><b></b></big></div>
	<div id="product_description"></div>
</div> <!-- id="product" -->


<div id="main">


<!-- Menu -->

<div id="navigation">
<br/>
<h1>colorizer</h1>


<ul>
  <li><a href="../index.html">Index</a></li>
</ul>



<h2>Modules</h2>
<ul class="nowrap">
  <li><a href="../modules/colorizer.html">colorizer</a></li>
  <li><a href="../modules/colorizer.buffer.html">buffer</a></li>
  <li><a href="../modules/colorizer.color.html">color</a></li>
  <li><a href="../modules/colorizer.config.html">config</a></li>
  <li><a href="../modules/colorizer.constants.html">constants</a></li>
  <li><a href="../modules/colorizer.matcher.html">matcher</a></li>
  <li><a href="../modules/colorizer.parser.rgb_hex.html">parser.rgb_hex</a></li>
  <li><a href="../modules/colorizer.parser.hsl.html">parser.hsl</a></li>
  <li><a href="../modules/colorizer.parser.names.html">parser.names</a></li>
  <li><a href="../modules/colorizer.parser.oklch.html">parser.oklch</a></li>
  <li><a href="../modules/colorizer.parser.rgb.html">parser.rgb</a></li>
  <li><a href="../modules/colorizer.parser.rgba_hex.html">parser.rgba_hex</a></li>
  <li><a href="../modules/colorizer.parser.xterm.html">parser.xterm</a></li>
  <li><a href="../modules/colorizer.sass.html">sass</a></li>
  <li><a href="../modules/colorizer.tailwind.html">tailwind</a></li>
  <li><strong>trie</strong></li>
  <li><a href="../modules/colorizer.usercmds.html">usercmds</a></li>
  <li><a href="../modules/colorizer.utils.html">utils</a></li>
</ul>

</div>

<div id="content">

<h1>Module <code>trie</code></h1>
<p>Trie implementation in LuaJIT.</p>
<p>
This module provides an optimized Trie data structure using LuaJIT's Foreign Function Interface (FFI).
It supports operations like insertion, search, finding the longest prefix, and converting the Trie into a table format.
<p>Dynamic Allocation:
<pre>
The implementation uses dynamic memory allocation for efficient storage and manipulation of nodes:
- Each Trie node dynamically allocates memory for its `children` and `keys` arrays using `ffi.C.malloc` and `ffi.C.realloc`.
- Arrays are initially allocated with a small capacity and are resized as needed to accommodate more child nodes.</pre>
<p>Node Structure:
Each Trie node contains the following fields:
<pre>
- `is_leaf` (boolean): Indicates whether the node represents the end of a string.
- `capacity` (number): The current maximum number of children the node can hold.
  - Starts at a small initial value (e.g., 8) and doubles as needed.
- `size` (number): The current number of children the node has.
  - Always ≤ `capacity`.
- `children` (array): A dynamically allocated array of pointers to child nodes.
- `keys` (array): A dynamically allocated array of ASCII values corresponding to the `children` nodes.</pre>
<p>Dynamic Resizing:
<pre>
- If a node's `size` exceeds its `capacity` during insertion, the `capacity` is doubled.
- The `children` and `keys` arrays are reallocated to match the new capacity using `ffi.C.realloc`.
- Resizing ensures efficient use of memory while avoiding frequent allocations.</pre>
<p>Memory Management:
<pre>
- Memory is manually managed:
  - Allocation: Done using `ffi.C.malloc` for new nodes and `ffi.C.realloc` for resizing arrays.
  - Deallocation: Performed recursively for all child nodes using `ffi.C.free`.
- The implementation includes safeguards to handle allocation failures and ensure proper cleanup.</pre></p>



<br/>
<br/>




</div> <!-- id="content" -->
</div> <!-- id="main" -->
<div id="about">
<i>generated by <a href="http://github.com/lunarmodules/LDoc">LDoc 1.5.0</a></i>
<i style="float:right;">Last updated - October </i>
</div> <!-- id="about" -->
</div> <!-- id="container" -->
</body>
</html>
